701. Insert into a Binary Search Tree

這題是一題類似於 2-3 樹中的插入操作，這道題可以用來理解如何保持樹的平衡。
在一棵**二叉搜索樹（BST）**中插入一個節點，並返回插入後的樹。

二叉搜索樹的性質：

• 左子樹的所有節點的值都小於根節點。
• 右子樹的所有節點的值都大於根節點。
• 左右子樹也分別是二叉搜索樹。

解題步驟

• 從根節點開始，根據節點值與 val 進行比較。
• 遞歸地在左子樹或右子樹中查找適當位置進行插入。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)  # 當遇到空位時插入新節點
    if val < root.val:
        root.left = insertIntoBST(root.left, val)  # 遞歸插入到左子樹
    else:
        root.right = insertIntoBST(root.right, val)  # 遞歸插入到右子樹
    return root

解題過程中的關鍵點

1. 保持二叉搜索樹的性質
   • 當插入的值比當前節點的值小時，進入左子樹。
   • 當插入的值比當前節點的值大時，進入右子樹。
2. 樹的平衡性
   • 插入操作本身並不涉及對樹的平衡性維護。如果題目要求樹保持平衡，可以考慮使用 AVL 樹或紅黑樹。